#ifndef UTILS_HASH_QUEUE_HPP
#define UTILS_HASH_QUEUE_HPP

/**
 * \file
 * \ingroup utility
 * \brief cas::hash_queue declaration.
 */

#include "utils/cxx-include.hpp"
#include "utils/core-module.hpp"

namespace cas
{
    /**
     * \ingroup utility
     * \brief Combination of linked-list (queue) and unordered_map (hash)
     *
     * Max item number (pool size) is fixed, use array (index) to emulate linked-list
     * STL-like coding style
     *
     * \tparam K key
     * \tparam T data
     */
    template <class K, class T>
    class hash_queue
    {
    public:
        hash_queue(); /**< must \c resize() before using */
        ~hash_queue();

        typedef typename std::unordered_map<K, size_t> hash_queue_map;
        typedef typename std::pair<K, T> hash_queue_pair;
        typedef typename hash_queue_map::iterator hash_queue_iterator;

        // pool control
        size_t capacity() const;         /**< return pool size */
        void clear();                    /**< clear all data */
        void resize(const size_t &size); /**< pool size expansion */
        size_t size() const;             /**< return item number */

        // item access
        void erase(const size_t &index);       /**< erase an item */
        void erase(const K &key);              /**< erase an item */
        hash_queue_iterator find(K key); /**< unordered_map::find */
        T *const get(const K &key);            /**< get pointer of data */
        T *const get(const size_t &index);     /**< get pointer of data */
        hash_queue_iterator map_end();         /**< unordered_map::end */
        void move_back(const size_t &index);   /**< update item as the most recent one */
        void move_back(const K &key);          /**< update item as the most recent one */
        void move_front(const size_t &index);  /**< update item as the least recent one */
        void move_front(const K &key);         /**< update item as the least recent one */
        /**
         * Insert item as the most recent one. When pool is full,
         * \c evict_front = \c true : evict the least recent one,
         * \c evict_front = \c false : abort current push operation.
         * \c key must not appear before.
         * \brief Insert item as most recent.
         * \param key key
         * \param data value
         * \return \c true if eviction happened.
         */
        bool push_back(K key, T data);
        bool push_front(K key, T data); /**< push item as least recent, if not full */
        hash_queue_pair pop_back();     /**< pop the most recent item */
        hash_queue_pair pop_front();    /**< pop the least recent item */

        // policy control
        void set_eviction(uint8_t policy); /**< 1=evict_front, 2=evict_back */

    private:
        struct hash_queue_node
        {
            K key{};               /**< \brief key */
            T data{};              /**< \brief stored data */
            size_t prev{SIZE_MAX}; /**< \brief previous node */
            size_t next{SIZE_MAX}; /**< \brief next node */
            size_t free{SIZE_MAX}; /**< \brief next free node */
        };

        bool evict_front{false}; /**< \brief when push_back() reaches capacity, evict front item if \c true, abort push if \c false */
        bool evict_back{false};  /**< \brief when push_front() reaches capacity, evict back item if \c true, abort push if \c false */

        hash_queue_node *pool{nullptr}; /**< \brief data pool */
        size_t pool_size{0};            /**< \brief maximum cache items */
        size_t used_size{0};            /**< \brief maximum index of used items */
        size_t item_size{0};            /**< \brief currently used items */
        size_t list_head{SIZE_MAX};     /**< \brief head of linked list */
        size_t list_tail{SIZE_MAX};     /**< \brief tail of linked list */
        size_t list_free{SIZE_MAX};     /**< \brief free list */

        hash_queue_map list_map; /**< map of linked list */

        void internal_erase(const size_t &index); /**< erase an item */
    };
} // namespace cas

#endif /* UTILS_HASH_QUEUE_HPP */
